home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 299_01 / readme.bp < prev    next >
Text File  |  1989-12-28  |  7KB  |  170 lines
  1. Back Propagation Generalized Delta Rule Learning Program
  2.  
  3. (c) 1989 by Ronald Michaels.  This program may be freely copied, 
  4. modified, transmitted, or used for any non-commercial purpose.
  5.  
  6.  Ronald Michaels
  7.  3 Wilmar Close, Greendale
  8.  Harare, Zimbabwe
  9.  
  10.  after 1 January 1990:
  11.  Ronald Michaels
  12.  231 Tipton Station Rd.
  13.  Knoxville, Tn. 37920
  14.  USA
  15.  
  16. I. Contents of this disk:
  17.  
  18.  bp.c      the main file
  19.  
  20.  error.c   handles error messages for bp.c
  21.  
  22.  error.h   header file for error.c
  23.  
  24.  random.c  a state of the art random number generator
  25.  
  26.  random.h  header file for random.c
  27.  
  28.  plot.c    contains functions to plot error graph for bp learning
  29.  
  30.  plot.h    header file for plot.h
  31.  
  32.  bp.exe    basic program without graphics
  33.  
  34.  bp_h.exe  program with Hercules graphics
  35.  
  36.  bp1.dat   bp looks here for the training patterns
  37.  
  38.  bp2.dat   bp looks here for program parameters
  39.  
  40.  xor.dat   training pattern set to illustrate the exclusive or problem
  41.  this is the problem used to prove the limitations of the 
  42.  single level perceptron by Minski and Papert.
  43.  
  44.  parity3.dat  training pattern set to illustrate a more difficult version 
  45.  of the xor problem
  46.  
  47.  parity4.dat  training pattern set to illustrate an even more difficult 
  48.  version of the xor problem
  49.  
  50.  test.c    a test driver for random.c
  51.  use this driver to test the random number generator for           
  52.  correctness if program is ported to non-80X86 environment
  53.  
  54.  readme    this file
  55.  
  56. II. Purpose of this program
  57.  
  58.  The purpose of this program is to illustrate the Back Propagation algorithm 
  59.  as outlined in the article:
  60.  
  61.  Rummelhart, Hinton & Williams. "Learning representations by back-
  62.  propagating errors". NATURE, vol. 329, 9 October 1986, pages 533-536.
  63.  
  64.  To this end, I have chosen to use the array representation rather than the 
  65.  linked list representation.  Vectors and matrices are allocated dynamically 
  66.  as one dimensional arrays and pointer arithmetic is used to access elements.  
  67.  This creates a fair amount of loop invariant code which the Zortech compiler 
  68.  evidently hoists; optimization cuts execution time in half.
  69.  
  70.  For the sake of simplicity I have used floating point representations for 
  71.  all patterns, weights, deltas, etc.  This means that without a math 
  72.  coprocessor this program will be SLOW.
  73.  
  74. III. How it works
  75.  
  76.  Back Propagation is a non-linear pattern recognition algorithm which 
  77.  overcomes one of the limitations of the single layer perceptron, that is the 
  78.  inability to learn to distinguish groups of data points which cannot be 
  79.  separated by a straight line or flat plane (or a hyper-plane in hyper-
  80.  space).
  81.  
  82.  This program looks for the file bp1.dat for the set of patterns to be 
  83.  learned.  Several pattern sets are provided, for example parity3.dat.  To 
  84.  use the algorithm to learn this set of patterns, do: copy parity3.dat 
  85.  bp1.dat.
  86.  
  87.  The file bp2.dat contains the learning rate and momentum parameters for the 
  88.  algorithm.  These may be altered to observe their effect on the algorithm.  
  89.  
  90.  bp.c contains the back propagation algorithm.  The function learn() is the 
  91.  heart of the program and the various steps in the algorithm are implemented 
  92.  as functions to be called from learn().  Output of the program can be 
  93.  character based or graphic depending on the value defined for GRAPH at the 
  94.  top of bp.c.  The graphics are for Hercules screens using the Zortech 
  95.  graphics library but can be rewritten easily.
  96.  
  97.  See the bp.c source code for descriptions of the individual functions which 
  98.  are called from learn().
  99.  
  100.  In the bp.c file there are several activation functions which may be tried 
  101.  in lieu of the sigmoid function used by Rummelhart, et al.  Since we are 
  102.  using finite precision arithmetic, there is no such thing as real 
  103.  continuity; it is of interest to observe the effects of function shape.
  104.  
  105. IV. Compiling the program
  106.  
  107.  There are two options presented here - graphics output to Hercules graphics
  108.  and ASCII output
  109.  to compile program and incorporate graphics, set GRAPH to 1 in file bp.c
  110.  then compile and link bp.c, error.c, plot.c, and random.c.
  111. to compile program with only ASCII output, set GRAPH to 0 in bp.c
  112.  then compile and link bp.c, error.c, and random.c.
  113.  This program compiles under the Zortech c compiler V. 1.07 as is.
  114.  With minor changes it will compile under Ecosoft V.4.07.
  115.  All functions are prototyped so older compilers will require changes to 
  116.  function declarations.
  117.  Note that graphics function calls and coordinates in plot.c must be revised 
  118.  to suit the graphics library employed.  If a display other than Hercules 
  119.  graphics is used for graphics, function prt_scr in plot.c must be revised to 
  120.  reflect the mapping of video memory.
  121.  
  122. V. Running the program
  123.  
  124.  First the program asks for a seed for the pseudorandom number generator.  
  125.  The number of learning cycles required for convergence is sensitive to the 
  126.  initial value of weights so the use of random.c should allow predictable 
  127.  pseudorandom weights independent of any specific compiler library and allow 
  128.  results from one implementation to be directly compared to results from 
  129.  another.
  130.  
  131.  Next the program asks for the upper and lower limits for the random numbers 
  132.  used to initialize the weights.  As mentioned above, the algorithm is 
  133.  sensitive to initial weights.
  134.  
  135.  Once the random weight parameters are selected, the program enters its main 
  136.  control loop.  Commands available are selected by pressing the first letter 
  137.  of the command.
  138.     
  139.     Learn:  Run the learning algorithm.  User is asked to specify the number 
  140.  of cycles.  From, say, 50 to 5000 cycles may be required to reach 
  141.  convergence depending upon starting point, leaning rate, and 
  142.  patterns to be learned.
  143.  
  144.     Recognize:  Present input patterns to weight matrices and calculate 
  145.  outputs.  Compare outputs to target outputs and calculate error.
  146.  
  147.     Dump:  Dump program variables to file bp3.dat for later review.  Caution, 
  148.  this command can build big files.
  149.  
  150.     Quit:  Terminate program   
  151.  
  152. VI. Further Reading
  153.  
  154.  Jones, William P. and Hoskins, Josiah. "Back-Propagation A generalized 
  155.  delta learning rule". Byte October 1987. pages 155-162.
  156.  
  157.  Rummelhart, David E. and McClelland, James L. Parallel Distributed 
  158.  Processing:Explorations in the Microstructure of Cognition. Cambridge: MIT 
  159.  Press, 1986.
  160.  
  161.  For an overview of artificial neural systems see the March 1988 issue of 
  162.  Computer published by the Computer Society of the IEEE.
  163.  
  164.  For a historical review of pattern recognition see:
  165.  Tou, Julius T. and Gonzalez, Rafael C. Pattern Recognition Principles. 
  166. Reading, Mass.: Addison-Wesley Publishing Company.
  167.  
  168.  For a good, inexpensive introduction to Neural Networks see:
  169.  Vemuri, V. (editor) Artificial Neural Networks: Theoretical Concepts. 
  170.  Washington, D.C. Computer Society Press Society Press of the IEEE.